package day2;

import java.util.*;

public class ch2 {


    //560
    public int subarraySum(int[] nums, int k) {
        int all = 0;
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if(map.containsKey(sum-k)){
                all+=map.get(sum-k);
            }
            int n = map.getOrDefault(sum,0);
            map.put(sum,n+1);
        }

        return all;
    }

    //239
    public int[] maxSlidingWindow(int[] nums, int k) {

        int sum = 0;
        int max = Integer.MIN_VALUE;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]==b[0]?b[1]-a[1]:b[0]-a[0]);


        int[] arr = new int[nums.length-k+1];

        for(int i=0;i<k-1;i++){
            pq.offer(new int[]{nums[i],i});
        }
        for(int i=k-1;i<nums.length;i++){
            pq.offer(new int[]{nums[i],i});
            while (pq.peek()[1]<i-k+1){
                pq.poll();
            }
            arr[i-k+1]=pq.peek()[0];
        }
        return arr;

    }


    //76
    public String minWindow(String s, String t) {
        if(s.length()<t.length()){
            return "";
        }
        HashMap<Character,Integer> exp = new HashMap<>();
        HashMap<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            int n = exp.getOrDefault(t.charAt(i),0);
            exp.put(t.charAt(i),n+1);
        }
        int lt = 0;
        String str = "";
        int min = Integer.MAX_VALUE;
        for (int rt = 0; rt < s.length(); rt++) {
            int n = map.getOrDefault(s.charAt(rt),0);
            map.put(s.charAt(rt),n+1);
            while (cal(map,exp)){
                if((rt+1-lt)<min){

                    str = s.substring(lt,rt+1);
                    min = str.length();
                }
                int p = map.get(s.charAt(lt));
                map.put(s.charAt(lt),p-1);
                lt++;
            }



        }
        return str;



    }

    public boolean cal(HashMap<Character,Integer> map,HashMap<Character,Integer> exp){
        for(Character ch:exp.keySet()){
            if(!map.containsKey(ch)){
                return false;
            }else {
                if(!map.get(ch).equals(exp.get(ch))){
                    return false;
                }
            }
        }

        return true;
    }




    public static void main(String[] args) {



    }
}
